//
// Created by ching on 2023/4/10.
//

/*
问题描述
设 T 是一棵带权树，树的每一条边带一个正权。又设 S 是 T 的顶点集,T/S 是从树 T 中 将 S 中顶点删去后得到的森林。如果 T/S 中所有树的从根到叶的路长都不超过 d ，则称 T/S 是一个 d 森林。
(1)设计一个算法求 T 的最小顶点集 S，使 T/S 是 d 森林。(提示:从叶向根移动)
(2)分析算法的正确性和计算复杂性。
(3)设 T 中有 n 个顶点，则算法的计算时间复杂性应为 。

对于给定的带权树，编程计算最小分离集 S。
*/
#include <iostream>
#include <fstream>

using namespace std;

struct Node {
    Node* parent = NULL;
    int distance = 0;
    int whole_distance = 0;
    bool cut = false;
    int out_degree = 0;

    //为了显示树增加3个属性，与计算无关。
    int index = 0;
    Node** children = NULL;
    int children_count = 0;
};

class Queue {
private:
    Node* array[1000];
    int head = 0;
    int tail = 0;

public:
    void push(Node* node) {
        array[tail++] = node;
    }

    Node* pop() {
        Node* node = array[head++];
        return node;
    }

    bool isEmpty() {
        return head == tail;
    }
};

class DTree {
private:
    Node* nodes;
    Node* root;
    int n;
    int d;

public:
    DTree(int n, int d, istream &in = cin) {
        this->n = n;
        this->d = d;
        nodes = new Node[n];
        for(int i = 0; i < n; i++) {
            Node* parent = &nodes[i];
            parent->index = i;
            in >> parent->children_count;
            parent->out_degree = parent->children_count;
            if(parent->children_count > 0) {
                parent->children = new Node*[parent->children_count];
                for (int j = 0; j < parent->children_count; j++) {
                    int child_index, child_distance;
                    in >> child_index >> child_distance;
                    Node *child = &nodes[child_index];
                    child->distance = child_distance;
                    child->parent = parent;
                    parent->children[j] = child;
                }
            }
        }
        root = &nodes[0];
    }

    void print(Node* node, int indent = 0, ostream &out = cout) {
        for(int i = 0; i < indent; i++) out << "  ";
        out << (node->cut ? "[X]Node" : "Node") << node->index << "(d=" <<  node->distance << ")" << endl;
        for(int i = 0; i < node->children_count; i++)
            print(node->children[i], indent + 1, out);
    }

    void print(ostream &out = cout) {
        print(root, 0, out);
    }

    void digraph(ostream &out = cout) {
        out << "digraph {" << endl;
        for(int i = 0; i < this->n; i++) {
            Node* node = &nodes[i];
            out << "\t" << i << (node->cut ? "[color=red];" : ";") << endl;
            for(int j = 0; j < node->children_count; j++) {
                Node* child = node->children[j];
                out << "\t" << i << "->" << child->index
                    << "[label=" << child->distance
                    << (node->cut || child->cut ? ",style=dashed];" : "];") << endl;
            }
        }
        out << "}";
    }

    int solution() {
        Queue queue;
        int cut_count = 0;
        for(int i = n - 1; i >= 0; i--) {
            Node* node = &nodes[i];
            if(node->out_degree == 0) {
                queue.push(node);
            }
        }
        while(!queue.isEmpty()) {
            Node* node = queue.pop();
            Node* parent = node->parent;
            if(parent && !parent->cut && node->whole_distance + node->distance > d) {
                parent->cut = true;
                cout << "[X]Node" << parent->index << " cut" << endl;
                parent = parent->parent;
                cut_count++;
            } else if(!node->cut && parent && parent->whole_distance < node->whole_distance + node->distance) {
                parent->whole_distance = node->whole_distance + node->distance;
            }
            if(parent && --parent->out_degree == 0) queue.push(parent);
        }
        return cut_count;
    }
};

int main() {

    int n, d;

    /* 终端输入
    cin >> n >> d;
    DTree tree(n, d);
    */

    /* 直接从文件读入 */
    ifstream fin("1000_295.txt", ios::in);
    fin >> n >> d;
    DTree tree(n, d, fin);
    fin.close();

    //tree.digraph();
    //cout << endl << endl << endl;

    cout << tree.solution() << " nodes cut for solution!" << endl;
    cout << endl << endl << endl;

    ofstream fout("dTree2.gv", ios::out);
    tree.digraph(fout);
    fout.close();

    return 0;
}